//根据一棵树的中序遍历与后序遍历构造二叉树。 
//
// 注意: 
//你可以假设树中没有重复的元素。 
//
// 例如，给出 
//
// 中序遍历 inorder = [9,3,15,20,7]
//后序遍历 postorder = [9,15,7,20,3] 
//
// 返回如下的二叉树： 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7
// 
// Related Topics 树 深度优先搜索 数组 
// 👍 264 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * Java：从中序与后序遍历序列构造二叉树
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P106_ConstructBinaryTreeFromInorderAndPostorderTraversal {
    public static void main(String[] args) {
        Solution solution = new P106_ConstructBinaryTreeFromInorderAndPostorderTraversal().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        Map<Integer, Integer> inMap = new HashMap<>();
        int[] postArr;

        public TreeNode buildTree(int[] inorder, int[] postorder) {
            postArr = postorder;
            for (int i = 0; i < inorder.length; i++) {
                inMap.put(inorder[i], i);
            }
            return buildTree(postorder.length - 1, 0, inorder.length - 1);
        }

        private TreeNode buildTree(int postRootIndex, int inLeftBound, int inRightBound) {
            if (inLeftBound > inRightBound) {
                return null;
            }
            TreeNode root = new TreeNode(postArr[postRootIndex]);
            int inRootIndex = inMap.get(postArr[postRootIndex]);
            root.left = buildTree(postRootIndex - (inRightBound - inRootIndex) - 1, inLeftBound, inRootIndex - 1);
            root.right = buildTree(postRootIndex -1, inRootIndex + 1, inRightBound);
            return root;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}